#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
/*
零钱兑换问题1：
给定n种硬币，第i种硬币的面值为value[i-1]
,目标金额为target
,每种硬币可以重复选取，问能够凑出目标金额的最少硬币数量。如果无法凑出目标金额，则返回-1。
当可选择的硬币种类为0时，无法凑出目标金额
*/
int coinChangeDP(int target, const vector<int> &values) {
  int n = values.size();
  int MAX = target + 1;
  vector<vector<int>> dp(n + 1, vector<int>(target + 1, 0));
  for (int i = 0; i <= target; i++) {
    dp[0][i] = MAX;
  }
  for (int i = 1; i <= n; i++) {
    for (int a = 1; a <= target; a++) {
      if (a < values[i - 1]) {
        dp[i][a] = dp[i - 1][a];
      } else {
        dp[i][a] = min(dp[i - 1][a], dp[i][a - values[i - 1]] + 1);
      }
    }
  }
  return dp[n][target] == MAX ? -1 : dp[n][target];
}

int coinChangeDP_space(int target, const vector<int> &values) {
  int n = values.size();
  int MAX = target + 1;
  // 初始为i=0时的状态, i=0为没有硬币可以选择,
  vector<int> dp(target + 1, MAX);
  dp[0] = 0;
  for (int i = 1; i <= n; i++) {
    for (int a = 1; a <= target; a++) {
      if (a < values[i - 1]) {
        dp[a] = dp[a];
      } else {
        dp[a] = min(dp[a], dp[a - values[i - 1]] + 1);
      }
    }
  }
  return dp[target] == MAX ? -1 : dp[target];
}

/*
零钱兑换问题2：
给定n种硬币，第i种硬币的面值为value[i-1]
,目标金额为target
,每种硬币可以重复选取，问能够凑出目标金额的方案数量。
*/
int coinChangeDP2(int target, const vector<int> &values) {
  int n = values.size();
  vector<vector<int>> dp(n + 1, vector<int>(target + 1, 0));
  // 目标金额为0 只有一种方案
  for (int i = 0; i <= n; i++) {
    dp[i][0] = 1;
  }
  for (int i = 1; i <= n; i++) {
    for (int a = 1; a <= target; a++) {
      if (a < values[i - 1]) {
        dp[i][a] = dp[i - 1][a];
      } else {
        // 选当前硬币和不选当前硬币的方案之和
        dp[i][a] = dp[i - 1][a] + dp[i][a - values[i - 1]];
      }
    }
  }
  return dp[n][target];
}

int coinChangeDP2_space(int target, const vector<int> &values) {
  int n = values.size();
  vector<int> dp(target + 1, 0);
  // 目标金额为0 只有一种方案
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int a = 1; a <= target; a++) {
      if (a < values[i - 1]) {
        dp[a] = dp[a];
      } else {
        // 选当前硬币和不选当前硬币的方案之和
        dp[a] = dp[a] + dp[a - values[i - 1]];
      }
    }
  }
  return dp[target];
}
int main() {
  vector<int> cions{1, 2, 5};
  int target = 5;
  //   int num = coinChangeDP(target, cions);
  int num = coinChangeDP2_space(target, cions);
  cout << num << endl;
}